//题目:
// 给定一个32位整数 num，你可以将一个数位从0变为1。请编写一个程序，找出你能够获得的最长的一串1的长度。

// 示例 1：
// 输入: num = 1775(110111011112)
// 输出: 8

// 示例 2：
// 输入: num = 7(01112)
// 输出: 4
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    int reverseBits(int num) 
    {
        //预备操作：拿到num的二进制数
        vector<int> nums;
        if(num<0) nums.push_back(1);
        else nums.push_back(0);
        for(int i=30;i>=0;i--)
        {
            if((num & (1<<i)) != 0)  nums.push_back(1);
            else  nums.push_back(0);
        }
        //动态规划
        //1.创建dp表————dp[i][0]表示：从左往右，以nums[i]为结尾的1子串最大长度（没有翻转过0）;dp[i][1]表示：从左往右，以nums[i]为结尾的1子串最大长度（已经翻转过0）
        vector<vector<int>> dp(32,vector<int>(2));
        //2.初始化
        if(nums[0]==0)dp[0][0]=0,dp[0][1]=1;
        else dp[0][0]=1,dp[0][1]=-0xffffff;//-0xffffff表示不存在
        //3.填表————动态转移方程：if(nums[i]==1) dp[i][0]=max(dp[i-1][0],dp[i-1][1])+1; else dp[i][1]=dp[i-1][]
        int ret=0;
        for(int i=1;i<32;i++)
        {
            if(nums[i]==1) 
            {
                dp[i][0]=dp[i-1][0]+1;//dp[i][0]表示未使用翻转的~~
                //在nums[i]前，使用过翻转，以后就不能再使用了~~
                dp[i][1]=dp[i-1][1]==-0xffffff?dp[i-1][1]:dp[i-1][1]+1;
            }
            else
            {
                dp[i][0]=0;
                dp[i][1]=1+dp[i-1][0];//翻转第i个，就要求nums中前i个不能被翻转过
            }
            int max_value=max(dp[i][0],dp[i][1]);
            ret=max(ret,max_value);
        }
        return ret;
    }
};